import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Stack;

public class Test2 {
    //归并排序
    private static void mergeSort(int[] array) {
        //merge(array,0,array.length-1);
        int gap = 1;
        while(gap < array.length) {
            for (int i = 0; i < array.length; i+=gap*2) {
                int mid = i+gap-1;
                if(mid >= array.length) {
                    mid = array.length-1;
                }
                int end = mid+gap;
                if(end >= array.length) {
                    end = array.length-1;
                }
                merge_sort(array,i,mid,end);
        }

            gap *= 2;
        }
    }

    private static void merge(int[] array,int start,int end) {
        if(start == end) {
            return;
        }

//        //int mid = (start + end) / 2;
//
//        //分解
//        merge(array,start,mid);
//        merge(array,mid+1,end);
//
//        //合并
//        //merge_sort(array,start,mid,end);

    }

    //合并两个有序数组
    private static void merge_sort(int[] array,int start,int mid,int end) {
        int[] tmp = new int[end-start+1];

        int s1 = start;
        int e1 = mid;
        int s2 = mid+1;
        int e2 = end;
        int k = 0;

        while(s1 <= e1 && s2 <= e2) {
            if(array[s1] < array[s2]) {
                tmp[k++] = array[s1++];
            } else {
                tmp[k++] = array[s2++];
            }
        }

        while(s1 <= e1) {
            tmp[k++] = array[s1++];
        }

        while(s2 <= e2) {
            tmp[k++] = array[s2++];
        }

        //放回到原数组中
        for(int i=0; i<k;i++) {
            array[i+start] = tmp[i];
        }
    }

    public static void countSort(int[] array) {
        //找到最值
        int max = array[0];
        int min = array[0];
        for (int i = 1; i < array.length; i++) {
            if(array[i] > max) {
                max = array[i];
            }
            if(array[i] < min) {
                min = array[i];
            }
        }
        int[] tmp = new int[max-min+1];

        for (int i = 0; i < array.length; i++) {
            tmp[array[i] - min]++;
        }

        int k = 0;
        for (int i = 0; i < tmp.length; i++) {
            while(tmp[i] != 0) {
                array[k++] = i+min;
                tmp[i]--;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {1,5,8,4,5,2,3,9,6,10,45};
        mergeSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
